//046. 另一个哥德巴赫猜想
//        哥德巴赫曾经提出任何一个奇合数都可以被写成一个质数和一个平方数的两倍的和，如：
//        然而最终发现这个猜想是错误的，求最小的不能被写成一个质数和一个平方数的两倍之和的
//        奇合数。
//        答案：5777

import java.util.LinkedList;
import java.util.List;

public class Week046 {
    /*
     *@ prime[i] :第i+1个素数
     *@ mv[i]    :i的最小质因子
     *@ 质数的最小质因子为它本身
     *@ 请不要更改传入的数组的值（即全为0）
     */
    // 欧拉筛1~n的素数
    static int[] prime, mv;

    public static int getPrime(int n) {
        int tot = 0;
        for (int i = 2; i <= n; ++i) {
            if (mv[i] == 0) {
                prime[tot++] = i;
                mv[i] = i;
            }
            for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
                mv[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
        return tot;
    }

    static boolean isPrime(int x) {
        return mv[x] == x;
    }

    static boolean check(int n) {
        for (int i = 1; 2 * i * i < n; ++i) {
            if (isPrime(n - 2 * i * i)) {
                return true;
            }
        }
        return false;
    }

    static void run() {
        final int n = 10000;
        prime = new int[n + 1];
        mv = new int[n + 1];
        getPrime(n);
        for (int i = 3; true; i += 2) {
            if (!isPrime(i) && !check(i)) {
                System.out.println(i);
                return;
            }
        }
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
